package eleventh.Comparable接口;

/**
 * 二“使用比较器进行排序操作”讲的排序过程其实也就是数据结构中的二叉树的排序结构
 * 即通过二叉树进行排序，然后利用中序遍历的方式把内容依次读取出来
 * <p>
 * 二叉树排序的基本原理就是：将第一个内容作为根节点保存，如果后面的值比根节点的值小，则放在根节点的左子树，如果后面的值比根节点的值大，
 * 则放在根节点的右子树
 */
// Integer为Comparable接口实例化
    /*
    下面按照以上的思路编写一个简单的二叉树排序操作，此处为了简化代码，直接使用Integer，因为Integer类本身也已经实现了Comparable接口
     */
class BinaryTree {
    class Node {     // 声明一个节点类
        private Comparable data;    // 保存具体内容
        private Node left;
        private Node right;

        public void addNode(Node newNode) {
            // 要确定是放在左子树还是右子树上
            if (newNode.data.compareTo(this.data) < 0) {
                // 放在左子树上
                if (this.left == null) {
                    this.left = newNode;
                } else {
                    this.left.addNode(newNode);
                }
            }
            if (newNode.data.compareTo(this.data) > 0) {
                // 放在右子树上
                if (this.right == null) {
                    this.right = newNode;
                } else {
                    this.right.addNode(newNode);
                }
            }
        }

        public void printNode() {   // 输出时采用中序遍历
            if (this.left != null) {    // 先输出左子树
                this.left.printNode();
            }
            System.out.print(this.data + "\t");// 再输出根节点
            if (this.right != null) {
                this.right.printNode();
            }
        }
    }

    private Node root;  // 根元素

    public void add(Comparable data) {
        Node newNode = new Node();  // 每传入一个新的内容就声明一个根节点
        newNode.data = data;
        if (root == null) {
            root = newNode;// 如果是第一个元素，则设置成根元素
        } else {
            root.addNode(newNode);// 确定节点是放在左子树还是右子树
        }
    }

    public void print() {    // 输出节点
        this.root.printNode();
    }

}

public class 分析比较器的排序原理 {
    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        bt.add(1);//加入重复元素
        bt.add(8);
        bt.add(3);
        bt.add(8);
        bt.add(18);
        bt.add(5);
        bt.add(5);
        System.out.println("排序之后的结果：");
        bt.print();
    }
}
/*
D:\WorkSpaces\Java\jdk-21\bin\java.exe "-javaagent:D:\Software\IntelliJ IDEA\IntelliJ IDEA 2023.3.2\lib\idea_rt.jar=57602:D:\Software\IntelliJ IDEA\IntelliJ IDEA 2023.3.2\bin" -Dfile.encoding=UTF-8 -Dsun.stdout.encoding=UTF-8 -Dsun.stderr.encoding=UTF-8 -classpath D:\WorkSpaces\JavaDevelopBase_start_329\out\production\JavaDevelopBase_start_329 eleventh.Comparable接口.分析比较器的排序原理
排序之后的结果：
1	3	5	8	18
Process finished with exit code 0

 */